home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cocktail / doc.lha / doc.doc / ooags.doc < prev    next >
Text File  |  1992-09-25  |  37KB  |  1,074 lines
  1.  
  2.  
  3.  
  4.  
  5.  
  6.  
  7.  
  8.  
  9.  
  10.  
  11. ___________________________________________________________________
  12.  
  13.  
  14.                                    Object-Oriented
  15.                                    Attribute Grammars
  16.  
  17.                                    J. Grosch
  18.  
  19.  
  20. ___________________________________________________________________
  21.  
  22.  
  23.  
  24.  
  25.  
  26.  
  27.  
  28.  
  29.  
  30.  
  31.  
  32.  
  33.  
  34.  
  35.  
  36.  
  37.  
  38.  
  39.  
  40.  
  41.  
  42.  
  43.  
  44.  
  45.  
  46.  
  47.  
  48.  
  49.  
  50. ___________________________________________________________________
  51.                                    GESELLSCHAFT FUeR MATHEMATIK
  52.                                    UND DATENVERARBEITUNG MBH
  53.  
  54.                                    FORSCHUNGSSTELLE FUeR
  55.                                    PROGRAMMSTRUKTUREN
  56.                                    AN DER UNIVERSITAeT KARLSRUHE
  57. ___________________________________________________________________
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75.                                    Project
  76.  
  77.                              Compiler Generation
  78.  
  79.          ___________________________________________________________
  80.  
  81.                       Object-Oriented Attribute Grammars
  82.  
  83.  
  84.                                  Josef Grosch
  85.  
  86.  
  87.                                 Aug. 27, 1990
  88.  
  89.          ___________________________________________________________
  90.  
  91.  
  92.                                 Report No. 23
  93.  
  94.  
  95.                              Copyright c 1990 GMD
  96.  
  97.  
  98.             Gesellschaft fuer Mathematik und Datenverarbeitung mbH
  99.                 Forschungsstelle an der Universitaet Karlsruhe
  100.                           Vincenz-Priesznitz-Str. 1
  101.                                D-7500 Karlsruhe
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
  113.  
  114.  
  115.  
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.                                                                              1
  135.  
  136.  
  137.                       Object-Oriented Attribute Grammars
  138.  
  139.  
  140.                                  Josef Grosch
  141.               GMD Forschungsstelle an der Universitaet Karlsruhe
  142.              Vincenz-Priesznitz-Str. 1, D-7500 Karlsruhe, Germany
  143.                            grosch@karlsruhe.gmd.de
  144.  
  145.  
  146. Abstract   This paper introduces object-oriented  attribute  grammars.   These
  147. can  be  characterized  as  a  notation for all classes of attribute grammars.
  148. Based on a subtype relation between grammar rules, inheritance  of  attributes
  149. and  attribute  computations are defined. With this approach, attributes local
  150. to grammar rules and the elimination of chain rules are possible  without  any
  151. special constructs.  We present object-oriented attribute grammars by a formal
  152. definition and by a few typical examples. They are compared to the concepts of
  153. related  areas.  We conclude by sketching an implementation of object-oriented
  154. attribute grammars as specification language of an attribute evaluator genera-
  155. tor  called  Ag  which  processes ordered attribute grammars (OAGs) and higher
  156. order attribute grammars (HAGs). A first realistic application showed that the
  157. generated  attribute  evaluators are very efficient and can be used in produc-
  158. tion quality systems.
  159.  
  160. 1.  Introduction
  161.  
  162.      This paper defines a  notation  for  attribute  grammars  called  object-
  163. oriented  attribute  grammars.  The  notation can be used to describe concrete
  164. syntax, abstract syntax, and attribute grammars in a uniform way.  Our  origi-
  165. nal  research  goal  was  to  promote  the acceptance of attribute grammars by
  166. improving the specification language and by generating evaluators that are  as
  167. efficient as possible.
  168.  
  169.      Many existing attribute grammar systems [DJL88] are based on the concrete
  170. syntax  of  the  source language.  It has several advantages to base attribute
  171. grammars on the abstract syntax, however. Most of  the  terminal  symbols  and
  172. chain  rules  disappear. This makes the specification shorter and clearer. The
  173. abstract syntax can be optimized towards the task of semantic  analysis.  Usu-
  174. ally,  this  leads  to  fewer grammar rules, fewer attribute computations, and
  175. fewer nodes in the structure tree.  The result  is  a  simplification  of  the
  176. attribute  grammar  as  well as a reduction of space and run time because less
  177. nodes have to be stored and visited during  attribute  evaluation.   Therefore
  178. efficiency is increased.  In this paper we assume that attribute evaluation is
  179. performed on the basis of an attributed tree which is stored in memory.
  180.  
  181.      The roots for our definition of object-oriented  attribute  grammars  can
  182. already  be  found in the implementation of current attribute grammar systems.
  183. In attribute grammars, nonterminals can be associated with  a  set  of  attri-
  184. butes. There may be several grammar rules having this nonterminal as left-hand
  185. side symbol. The implementation of attributed trees uses a separate node  type
  186. for  every  grammar rule. Now all node types for one nonterminal have to store
  187. the attributes of this nonterminal. This leads to the inheritance of  informa-
  188. tion  from  a  nonterminal to the associated rules.  Object-oriented attribute
  189. grammars generalize this observation. Besides attributes, right-hand sides and
  190.  
  191.  
  192.  
  193.  
  194.  
  195.  
  196.  
  197.  
  198.  
  199.  
  200.                                                                              2
  201.  
  202.  
  203. attribute  computations can be inherited as well. Inheritance is extended from
  204. one level (from nonterminals to rules) to arbitrary  many  levels.  Attributes
  205. local to a rule can be introduced without any special construct.
  206.  
  207.      The rest of this paper is organized as follows: The next section  defines
  208. object-oriented  attribute  grammars formally.  Section 3 presents examples of
  209. object-oriented attribute grammars using  the  specification  language  of  an
  210. attribute  grammar system.  Section 4 compares object-oriented attribute gram-
  211. mars to the concepts of conventional attribute  grammars,  trees,  types,  and
  212. object-oriented  programming.  Section 5 shortly sketches an implementation of
  213. object-oriented attribute grammars and reports early experiences from  a  non-
  214. trivial application project.
  215.  
  216. 2.  Definition
  217.  
  218.      This section defines the principles of  object-oriented  attribute  gram-
  219. mars.   As  starting  point  we  shortly  recall the traditional definition of
  220. attribute grammars [Knu68, Knu71].
  221.  
  222.      An attribute grammar is  an  extension  of  a  context-free  grammar.   A
  223. context-free grammar is denoted by G = (N, T, P, Z) where N is the set of non-
  224. terminals, T is the set of terminals, P is the set of productions, and Z  N is
  225. the start symbol, which cannot appear on the right-hand side of any production
  226. in P.  The set V = N U T is called the vocabulary.  Each production p   P  has
  227. the  form p: X -> A where X  N and A  V*.  The relation  (directly derives) is
  228. defined over strings in V* as follows: if p: X -> A, p   P,  @XC  V*,  @AC  V*
  229. then  @XC  @AC.   The  relation * is the transitive and reflexive closure of .
  230. The language L(G) is defined as L(G) = { w | Z * w }.
  231.  
  232.      An attribute grammar augments a context-free grammar  by  attributes  and
  233. attribute  computations. A set of attributes is associated with each symbol in
  234. V. Attribute computations are added to each production describing how to  com-
  235. pute  attribute  values.  This simple view of attribute grammars shall suffice
  236. for the scope of this paper.
  237.  
  238.      In general there can be several productions having the  same  nonterminal
  239. on  the  left-hand  side.  This allows for different derivations starting from
  240. one nonterminal. In object-oriented attribute grammars, one production is per-
  241. mitted  for  one  left-hand side symbol, only. This way the notions production
  242. and nonterminal (vocabulary respectively) become the same and are called  node
  243. type in the following. Several different derivations are made possible through
  244. the newly introduced subtype relation.
  245.  
  246.      An object-oriented attribute grammar is formally denoted by G = (N, T, A,
  247. C,  Z) where N is the set of nonterminals, T is the set of terminals, A is the
  248. set of attributes, C is the set of attribute computations, and Z is the  start
  249. symbol (Z  N).  The set NT = N U T is called the set of node types.  Each ele-
  250. ment n  NT is associated with a tuple n: (R, B, D,  S)  where  R  NT*  is  the
  251. right-hand side, B  A* is the set of attributes, D  C* is the set of attribute
  252. computations, and S  NT is the base type.
  253.  
  254.      The elements of NT induce a relation  (subtype) over NT  as  follows:  if
  255. n: (A, B, D, m)  NT  then  n   m.  m is called base or super type, n is called
  256.  
  257.  
  258.  
  259.  
  260.  
  261.  
  262.  
  263.  
  264.  
  265.  
  266.                                                                              3
  267.  
  268.  
  269. derived type or subtype.  The relation  is transitive: if n  m and m  o then n
  270.  o.
  271.  
  272.      The relation  (directly derives) is defined here only  for  the  context-
  273. free part of an object-oriented attribute grammar. There are two possibilities
  274. for derivations which are defined over strings in NT* as follows:
  275.  
  276.       if @niC  NT* andn1: (A1, B1, D1, n0)  NT,
  277.                n2: (A2, B2, D2, n1)  NT,
  278.                             . . .
  279.                ni: (Ai, Bi, Di, ni-1)  NT then @niC  @A1A2 . . . AiC.
  280.  
  281.       if @nC  NT* and m  n then @nC  @mC.
  282.  
  283. We assume the existence of a predefined node  type  n0: (, , , -)  with  empty
  284. components.  In  a  direct derivation step, a node type can be replaced by its
  285. right-hand side (A1 . . . Ai) or by one of its  subtypes  (m).  All  replacing
  286. right-hand  sides  are  the union of right-hand sides according to the subtype
  287. hierarchy.  The relation * is the transitive and reflexive closure of  .   The
  288. language L(G) is defined as L(G) = { w | Z * w }.
  289.  
  290.      The subtype relation has the following properties: a  derived  node  type
  291. inherits  the  right-hand side, the attributes, and the attribute computations
  292. from its base type. As consequence of the transitive nature of this  relation,
  293. a  derived  type  inherits all the components from all base types according to
  294. the subtype hierarchy.  It may extend the set of inherited items  by  defining
  295. additional  right-hand  side  elements, attributes, or attribute computations.
  296. All accumulated right-hand side  elements  and  attributes  must  be  distinct
  297. because  they  are  united.  An  attribute  computation  for  an attribute may
  298. overwrite an inherited one.  The definition of  the  subtype  relation  allows
  299. exactly single inheritance.
  300.  
  301. 3.  Examples
  302.  
  303.      We implemented an attribute grammar system called  Ag  based  on  object-
  304. oriented attribute grammars [GrE90]. The following examples of object-oriented
  305. attribute grammars are  given  in  the  specification  language  of  Ag.   The
  306. language  tries to adhere to the conventional style of grammars as far as pos-
  307. sible.  It offers far more features for practical usage than can be  explained
  308. here. The interested reader is referred to the user's manual [Gro89b].
  309.  
  310.     Example 1:
  311.     Expr        = <
  312.        Add      = Lop: Expr '+' Rop: Expr .
  313.        Sub      = Lop: Expr '-' Rop: Expr .
  314.        Const    = Integer .
  315.     > .
  316.     Integer     : .
  317.     '+'         : .
  318.     '-'         : .
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325.  
  326.  
  327.  
  328.  
  329.  
  330.  
  331.                                                                              4
  332.  
  333.  
  334.      Example 1 describes the concrete  syntax  of  primitive  expressions.  It
  335. defines four nonterminal node types (Expr, Add, Sub, and Const) and 3 terminal
  336. node types (Integer, '+', and '-').  The distinction between nonterminals  and
  337. terminals is based on the characters '=' and ':'.  Terminal node types without
  338. attributes do not have to be defined explicitly because undefined  node  types
  339. are defined implicitly as terminals. Node types can be named by identifiers or
  340. strings. In this example only the right-hand side components and  the  subtype
  341. relation  are used - attributes and attribute computations do not appear. Expr
  342. has zero, Add and Sub have three, and Const has one right-hand side element(s)
  343. or children. A child consists of a selector name and node type. Selector names
  344. are added to allow unambiguous access to children. Missing selector names  are
  345. implicitly  defined  to be equal to the name of the node type. The children of
  346. the node type Add have the selector names Lop, '+', and Rop.  Their node types
  347. are  Expr,  '+', and Expr. The node type Const has one child with the selector
  348. name Integer of type Integer.  The subtype relation is expressed by  enclosing
  349. all  subtypes  of a base type in < > brackets.  In Example 1 the subtype rela-
  350. tion is: Add  Expr, Sub  Expr, Const  Expr.
  351.  
  352.     Example 2:
  353.     Expr        = [Value: INTEGER]        { Value := 0; } <
  354.        Add      = Lop: Expr '+' Rop: Expr { Value := Lop:Value + Rop:Value; } .
  355.        Sub      = Lop: Expr '+' Rop: Expr { Value := Lop:Value - Rop:Value; } .
  356.        Const    = Integer                 { Value := Integer:Value; } .
  357.        Zero     = .
  358.     > .
  359.     Integer     : [Value: INTEGER] .
  360.  
  361.  
  362.      Example 2 adds attributes and attribute computations  to  Example  1  and
  363. describes the evaluation of expressions. Attribute definitions are in enclosed
  364. in [ ] brackets. Similarly to children,  attributes  are  characterized  by  a
  365. selector name and a certain type. The attribute types are given by names taken
  366. from the target language (here Modula-2).
  367.  
  368.      The node types Expr and Integer define one attribute named Value of  type
  369. INTEGER.  The  subtypes  Add, Sub, Const, and Zero inherit the attribute Value
  370. from Expr. Attribute computations are mainly written as assignments of  target
  371. language  expressions  to  attributes  and  are  enclosed in { } brackets. The
  372. attribute computations are expressed with respect to a current tree  node  and
  373. may  contain  so-called attribute denotations.  At a tree node, the attributes
  374. of this node and the attributes of the children are accessible. Attributes  of
  375. the  current node or of the left-hand side of a rule are denoted just by their
  376. name.  Attributes of a child or of the right-hand side of a rule  are  denoted
  377. by  the  child's  selector name, a colon, and the attribute name.  The subtype
  378. Zero inherits the computation of the attribute Value from the base type  Expr,
  379. whereas  the  node  types  Add,  Sub,  and  Const  overwrite it with node type
  380. specific computations.  The value for the attribute of the node  type  Integer
  381. has  to  be  provided  at  the  creation  time of the syntax tree e. g. from a
  382. scanner and parser.
  383.  
  384.      A node of a base type like Expr usually does not  occur  in  an  abstract
  385. syntax  tree  for  a complete program.  However, this node type can be used as
  386.  
  387.  
  388.  
  389.  
  390.  
  391.  
  392.  
  393.  
  394.  
  395.  
  396.                                                                              5
  397.  
  398.  
  399. placeholder for unexpanded nonterminals in incomplete programs which occur  in
  400. applications like syntax directed editors.
  401.  
  402.     Example 3:
  403.     Stats       = <
  404.        NoStat   = .
  405.        OneStat  = Stats Stat .
  406.     > .
  407.     Stat        = [Pos: tPosition] <
  408.        If       = Expr Then: Stats Else: Stats .
  409.        While    = Expr Stats .
  410.        Call     = Actuals [Ident: tIdent] .
  411.     > .
  412.  
  413.  
  414.     Example 4:
  415.     Stats       = <
  416.        NoStat   = .
  417.        Stat     = Next: Stats [Pos: tPosition] <
  418.           If    = Expr Then: Stats Else: Stats .
  419.           While = Expr Stats .
  420.           Call  = Actuals [Ident: tIdent] .
  421.        > .
  422.     > .
  423.  
  424.  
  425.      Examples 3 and 4 describe two possibilities for the specification of  the
  426. abstract  syntax of statement sequences. Both examples use two nonterminals to
  427. describe a sequence (Stats) and various statements (Stat). Whereas these  non-
  428. terminals are independent in Example 3 they are related as subtypes in Example
  429. 4. Therefore Example 4 shows a non-trivial subtype relation of  nesting  depth
  430. two.  The  subtype  relation  is: NoStat  Stats, Stat  Stats, If  Stat, While
  431. Stat, Call  Stat.  In Example 4 the node types If, While, and Call inherit the
  432. child  Next  of type Stats and the attribute Pos from the base type Stat. They
  433. add their own children and attributes (Call only). The big difference  between
  434. the two solutions arises with regard to efficiency. Example 3 allocates in the
  435. structure tree two nodes per statement in a sequence. These nodes  need  space
  436. and  have  to  be  traversed  (visited) during attribute evaluation. Example 4
  437. allocates only one node per statement thus saving both,  space  and  attribute
  438. evaluation  time.  The price is the additional child called Next in every node
  439. type for a statement. Nevertheless, it has to be defined only once because  of
  440. the inheritance mechanism.
  441.  
  442.      The node type Call uses a local attribute called Ident. There is no  need
  443. for  the  description  of a procedure call statement to have two children: the
  444. name of the procedure and the list of actual parameters. The name of the  pro-
  445. cedure  can  become a local attribute of the node type and therefore one child
  446. for the parameters suffices.
  447.  
  448.      The specification of node types can be grouped into modules. This feature
  449. can  be  used  to structure a specification or to extend an existing one. If a
  450. node type has already been declared the given children, attributes,  attribute
  451.  
  452.  
  453.  
  454.  
  455.  
  456.  
  457.  
  458.  
  459.  
  460.  
  461.                                                                              6
  462.  
  463.  
  464. computations, and subtypes are added to the existing declaration.  Otherwise a
  465. new node type is introduced.  This way of modularization offers several possi-
  466. bilities:
  467.  
  468. -    Context-free grammar and attribute declarations (= node types) as well as
  469.      attribute  computations can be combined in one module as in conventional,
  470.      monolithic attribute grammars.
  471.  
  472. -    The context-free grammar, the attribute declarations, and  the  attribute
  473.      computations can be placed in three separate modules.
  474.  
  475. -    The attribute computations can be subdivided into several modules accord-
  476.      ing  to  the  tasks  of  semantic  analysis.  For example, there would be
  477.      modules for scope handling, type determination, and context conditions.
  478.  
  479. -    The information can be grouped according to language concepts or  nonter-
  480.      minals. For example, there would be modules containing the grammar rules,
  481.      the attribute declarations, and the attribute computations  for  declara-
  482.      tions, statements, and expressions.
  483.  
  484.     Example:
  485.     MODULE my_version
  486.     Stats        = [Env: tEnv] <                    /* add attribute   */
  487.        While     = Init: Stats Terminate: Stats .   /* add children    */
  488.        Repeat    = Stats Expr .                     /* add node type   */
  489.     > .
  490.     Zero         = { Value := 1; }                  /* add computation */
  491.     END my_version
  492.  
  493.  
  494. 4.  Comparison
  495.  
  496.      This section compares object-oriented attribute grammars as introduced in
  497. this  paper  with  the  well-known  concepts of (attribute) grammars, tree and
  498. record types, type extensions, and object-oriented  programming.  These  areas
  499. are  related  because of the following reasons: attribute grammars are usually
  500. based on context-free grammars. An attribute grammar specifies  an  evaluation
  501. of  attributes of a tree defined by such a context-free grammar.  Trees can be
  502. implemented using a set of record type  declarations.  Therefore  context-free
  503. grammars,  trees,  and  record  types deal more or less with the same concept.
  504. Table 1 compares the most important notions from these areas. Additionally  we
  505. included  the  notions  from  the  area of object-oriented (oo) programming as
  506. described e. g. in [Bla89].
  507.  
  508.  
  509.  
  510.  
  511.  
  512.  
  513.  
  514.  
  515.  
  516.  
  517.  
  518.  
  519.  
  520.  
  521.  
  522.  
  523.  
  524.                                                                              7
  525.  
  526.  
  527.  
  528. (attribute) grammars    trees                  types                   oo-programming
  529. ________________________________________________________________________________________
  530. rule                    node type              record type             class
  531. attribute               field in a node type   record field            instance variable
  532. nonterminal             set of node types      union of record types   -
  533. terminal                distinct node type     record type without     -
  534.                                                   pointer fields
  535. rule application        tree node              record variable         object, instance
  536. attribute computation   -                      procedure declaration   method
  537. -                       -                      procedure call          message
  538. -                       -                      base type               superclass
  539. -                       -                      derived type            subclass
  540. -                       -                      extension               inheritance
  541.                      
  542.  
  543.  
  544.  
  545.  
  546.  
  547.  
  548.  
  549.  
  550.  
  551.  
  552.                                             
  553.  
  554.  
  555.  
  556.  
  557.  
  558.  
  559.  
  560.  
  561.  
  562.  
  563.                                                                     
  564.  
  565.  
  566.  
  567.  
  568.  
  569.  
  570.  
  571.  
  572.  
  573.  
  574.  
  575.  
  576. Table 1: Comparison of notions from the areas of grammars, trees, types, and oo-programming
  577.  
  578.  
  579.      Object-oriented attribute grammars are missing in Table 1.  For  them  we
  580. used the notions from attribute grammars and added the notions node type, base
  581. type, subtype or derived type, and inheritance from the other areas.
  582.  
  583. 4.1.  Attribute Grammars
  584.  
  585.      Conventional grammars in BNF allow several productions with the same non-
  586. terminal  symbol  on the left-hand side. A node type in object-oriented attri-
  587. bute grammars, which corresponds to a nonterminal as well as to a  rule  name,
  588. has  exactly  one right-hand side.  The selector names can be regarded as syn-
  589. tactic sugar.  To allow for several different derivations, a subtype  relation
  590. between node types is added.  During a derivation, a node type may be replaced
  591. by its right-hand side or by a  subtype.  Additionally,  the  subtype  feature
  592. allows  to  express chain rules and single inheritance. Inheritance is a nota-
  593. tion to factor out parts that are common to several node types such as  right-
  594. hand  sides,  attributes, and attribute computations.  Fortunately, attributes
  595. local to a rule (node type) are possible without any special construct.
  596.  
  597.      Object-oriented attribute grammars are a notation to write  BNF  grammars
  598. in  a  short  and  concise  way and where the underlying tree structure can be
  599. exactly described. With respect to  attribute  grammars  the  same  notational
  600. advantages  hold.   Attribute  grammars  are a special case of object-oriented
  601. attribute grammars. They are characterized by a one level  subtype  hierarchy,
  602. right-hand sides and attribute computations are defined for subtypes only, and
  603. attributes are associated only with base types.  In terms of attribute grammar
  604. classes  or attribute grammar semantics object-oriented attribute grammars are
  605. equivalent to attribute grammars.
  606.  
  607. 4.2.  Trees and Records
  608.  
  609.      When trees are stored in  memory,  they  can  be  represented  by  linked
  610. records.  Every node type corresponds to a record type. Object-oriented attri-
  611. bute grammars directly describe the structure of attributed syntax trees.  The
  612. node  types can be seen as record types. The right-hand side elements resemble
  613.  
  614.  
  615.  
  616.  
  617.  
  618.  
  619.  
  620.  
  621.  
  622.  
  623.                                                                              8
  624.  
  625.  
  626. pointer valued fields describing the tree structure  and  the  attributes  are
  627. additional  fields  for  arbitrary information stored at tree nodes. The field
  628. name and field type needed for record types are also present in the node types
  629. of object-oriented attribute grammars.
  630.  
  631. 4.3.  Type Extensions
  632.  
  633.      Type extensions have been introduced with the language  Oberon  by  Wirth
  634. [Wir88a, Wir88b, Wir88c].  They allow the definition of a record type based on
  635. an existing record type by adding  record  fields.  This  extension  mechanism
  636. induces  a  subtype relation between record types. The subtype and inheritance
  637. features are equivalent in object-oriented attribute grammars and type  exten-
  638. sions  with  the  difference  that  Wirth  uses the word extension in place of
  639. inheritance.
  640.  
  641. 4.4.  Object-Oriented Programming
  642.  
  643.      The concepts of subtype  and  inheritance  in  object-oriented  attribute
  644. grammars  and  object-oriented  programming  have  many  similarities and this
  645. explains the name object-oriented  attribute  grammars.   The  notions  class,
  646. instance  variable, object, superclass, and subclass have direct counter parts
  647. (see Table 1).  There are also some differences.  Object-oriented  programming
  648. allows  an arbitrary number of named methods which are activated by explicitly
  649. sending messages. In object-oriented attribute grammars there is  exactly  one
  650. attribute computation (unnamed method) for an attribute. There is nothing like
  651. messages: the attribute computation for an attribute is  activated  implicitly
  652. and exactly once.
  653.  
  654. 5.  Experiences
  655.  
  656.      As already mentioned, we implemented  an  attribute  evaluator  generator
  657. called  Ag  which  processes  object-oriented  attribute  grammars. It accepts
  658. ordered attribute grammars (OAGs) [Kas80] and higher order attribute  grammars
  659. (HAGs)  [VSK89]  which  are  a  reinvention  of  generative attribute grammars
  660. [Den84].  Ag is written in Modula-2 and runs under UNIX. The  sources  for  Ag
  661. also  exist in C.  Attribute evaluators in the target languages Modula-2 and C
  662. are supported.  We tried to avoid the disadvantages of closed and complex sys-
  663. tems.  Instead,  we had the goal of keeping everything as small, simple, open,
  664. powerful, efficient, practical usable, and language independent  as  possible.
  665. The  specification language has a concise and clear concrete syntax to support
  666. compact attribute grammars which are easy to write and to read. The  attribute
  667. grammars  are  oriented towards abstract syntax what is a great simplification
  668. in comparison to the use of concrete syntax. Readability of attribute grammars
  669. is  furthermore  supported by modules where the context-free grammar (abstract
  670. syntax) is specified only once in order to assure consistency.  The attributes
  671. are  typed using the types of the target language - tree-valued attributes are
  672. possible. The attribute computations are programmed in the target language and
  673. should  be written in a functional style. External functions can be called and
  674. non-functional statements as well as side-effects are possible. These features
  675. make  attribute  grammars  open  and allow the attributed trees as well as the
  676. attribute evaluators to be implemented efficiently.
  677.  
  678.  
  679.  
  680.  
  681.  
  682.  
  683.  
  684.  
  685.  
  686.  
  687.  
  688.                                                                              9
  689.  
  690.  
  691.      Using the target language for attribute computations makes the  generator
  692. largely target language independent because there is no need to analyze a spe-
  693. cial language for attribute computations and to generate code for it. This job
  694. is  already  performed  by usual compilers. Therefore Ag is a relatively small
  695. and simple program which  concentrates  on  the  analysis  of  object-oriented
  696. attribute  grammars  and  attribute dependencies.  It generates evaluators for
  697. (OAGs) and (HAGs).  The generated  attribute  evaluators  are  very  efficient
  698. because they are directly coded using recursive procedures.
  699.  
  700.      A large application of object-oriented attribute grammars and Ag was  the
  701. generation  of  the  semantic  analysis  phase  of  a Modula-2 to C translator
  702. [Mar90]. The program called Mtc translates Modula-2 programs into  readable  C
  703. code without any restrictions (even nested procedures and modules).  This pro-
  704. gram was largely generated using our compiler construction tool  box  [GrE90].
  705. Table  2  gives  the  sizes  of  the  specifications  and the generated source
  706. modules.
  707.  
  708.  
  709. ________________________________________________________________________________________
  710.  part                  specification          source module               tool
  711. ________________________________________________________________________________________
  712.                    formal   code   total   def.   impl.   total   name  references
  713. ________________________________________________________________________________________
  714.  scanner             392     133    525      56    1320    1376   Rex   [Gro87b, Gro88]
  715.  parser              951      88   1039      81    3007    3088   Ell   [Gro88, GrV88]
  716.  tree                189      51    240     579    2992    3571   Ast   [Gro89a]
  717.  symbol table        115     938   1053     413    1475    1888   Ast   [Gro89a]
  718.  semantics          1886     151   2037       9    3288    3297   Ag    [Gro89b]
  719.  code generator     2793     969   3762      47    7309    7356   Estra [Vie89]
  720.  reusable parts      -       -       -      819    2722    3541   Reuse [Gro87a]
  721.  miscellaneous       -       -       -      698    3153    3851
  722. ________________________________________________________________________________________
  723.  total              6326    2330   8656    2702   25266   27968
  724. ________________________________________________________________________________________
  725.  
  726.  
  727.  
  728.  
  729.  
  730.  
  731.  
  732.  
  733.  
  734.  
  735.  
  736.  
  737.                 
  738.  
  739.  
  740.  
  741.  
  742.  
  743.  
  744.  
  745.  
  746.  
  747.  
  748.  
  749.                                         
  750.  
  751.  
  752.  
  753.  
  754.  
  755.  
  756.  
  757.  
  758.  
  759.  
  760.  
  761.                                                                
  762.  
  763.  
  764.  
  765.  
  766.  
  767.  
  768.  
  769.  
  770.  
  771.  
  772.  
  773.                                                                                        
  774.  
  775.  
  776.  
  777.  
  778.  
  779.  
  780.  
  781.  
  782.  
  783.  
  784.  
  785.  
  786.  
  787.         Table 2: Sizes of the specifications and source modules of Mtc
  788.  
  789.  
  790.      The binary program comprises 301,240 bytes.  It runs at a  speed  of  810
  791. tokens  per second or 167 lines per second on a SUN workstation (MC 68020 pro-
  792. cessor). These figures are computed by taking only the size of the  translated
  793. modules  into account. If we include the definition modules which are imported
  794. transitively and which are scanned, parsed, and analyzed as well, we arrive at
  795. 1320  tokens  per second or 418 lines per second. In comparison, the compilers
  796. supplied by the manufacturer run at a speed of 97 lines per second  (excluding
  797. header  files) or 163 lines per second (including header files) in the case of
  798. C and 48 lines per second in the case of Modula-2. The run time of Mtc is dis-
  799. tributed as follows:
  800.  
  801.  
  802.                   scanning + parsing + tree construction   42 %
  803.                   semantic analysis                        33 %
  804.                   code generation                          25 %
  805.  
  806.  
  807.  
  808.  
  809.  
  810.  
  811.  
  812.  
  813.  
  814.  
  815.  
  816.                                                                             10
  817.  
  818.  
  819. The semantic analysis spends 95 % in attribute computations  using  user  sup-
  820. plied  code  and  5 % in tree traversal or visit actions respectively.  By the
  821. way, there are up to five visits to 11 node types.
  822.  
  823.      Mtc uses approximately 360 K Bytes dynamic memory per 1000  source  lines
  824. to  store  the  abstract  syntax  tree,  the  attributes, and the symbol table
  825. without optimization of attribute storage. Another 600 K Bytes are used by the
  826. transformer  generated with Estra.  This is bearable with today's memory capa-
  827. cities.  Contrary to the literature this shows that it is  possible  to  store
  828. all  attributes  in  the  tree. We even do this for the environment attribute.
  829. This becomes possible by implementing the symbol table  as  an  abstract  data
  830. type in the target language. The implementation is time and space efficient by
  831. taking advantage of pointer semantics and structure sharing.
  832.  
  833.      These results demonstrate the time efficiency of the generated  attribute
  834. evaluators  in  the  semantic analysis of non-trivial languages like Modula-2.
  835. The performance makes (object-oriented) attribute grammars and Ag  usable  for
  836. production quality systems.
  837.  
  838. 6.  Summary
  839.  
  840.      We introduced object-oriented attribute grammars as a common notation for
  841. concrete  syntax,  abstract  syntax,  and  attribute grammars. The subtype and
  842. inheritance features represent a shorthand notation  for  attribute  grammars.
  843. The advantages of object-oriented attribute grammars become primarily apparent
  844. when used in practice as specification language for an attribute grammar  sys-
  845. tem.   They  allow  the  exact description of the underlying tree structure in
  846. order to create compact and storage efficient trees. Right-hand side elements,
  847. attributes, and attribute computations common to several rules can be factored
  848. out. They allow the expression of chain rules and the definition of attributes
  849. local  to  rules.   We  compared object-oriented attribute grammars to similar
  850. concepts such as conventional attribute grammars, trees,  types,  and  object-
  851. oriented  programming.   An  attribute  evaluator generator system for object-
  852. oriented attribute grammars has been  implemented.   The  generated  attribute
  853. evaluators  are  very  efficient especially in terms of run time.  We reported
  854. early experiences from a non-trivial application which are quite satisfying.
  855.  
  856. References
  857.  
  858. [Bla89]
  859.      G.  Blaschek,  Implementation  of   Objects   in   Modula-2,   Structured
  860.      Programming 10, 3 (1989), 147-155.
  861.  
  862. [Den84]
  863.      P.   Dencker,   Generative   attributierte   Grammatiken,   Dissertation,
  864.      Universitat Karlsruhe, 1984.
  865.  
  866. [DJL88]
  867.      P. Deransart, M. Jourdan and B. Lorho, Attribute Grammars -  Definitions,
  868.      Systems and Bibliography, LNCS 323, (1988), , Springer Verlag.
  869.  
  870. [Gro87a]
  871.      J. Grosch, Reusable Software - A Collection of  Modula-Modules,  Compiler
  872.  
  873.  
  874.  
  875.  
  876.  
  877.  
  878.  
  879.  
  880.  
  881.  
  882.                                                                             11
  883.  
  884.  
  885.      Generation   Report  No.  4,  GMD  Forschungsstelle  an  der  Universitat
  886.      Karlsruhe, Sep. 1987.
  887.  
  888. [Gro87b]
  889.      J. Grosch, Rex - A Scanner Generator, Compiler Generation Report  No.  5,
  890.      GMD Forschungsstelle an der Universitat Karlsruhe, Dec. 1987.
  891.  
  892. [Gro88]
  893.      J. Grosch, Generators for High-Speed Front-Ends, LNCS 371,  (Oct.  1988),
  894.      81-92, Springer Verlag.
  895.  
  896. [GrV88]
  897.      J. Grosch and B. Vielsack, The Parser Generators Lalr and  Ell,  Compiler
  898.      Generation   Report  No.  8,  GMD  Forschungsstelle  an  der  Universitat
  899.      Karlsruhe, Apr. 1988.
  900.  
  901. [Gro89a]
  902.      J. Grosch, Ast - A Generator for Abstract Syntax Trees (Revised Version),
  903.      Compiler   Generation   Report   No.  15,  GMD  Forschungsstelle  an  der
  904.      Universitat Karlsruhe, Aug. 1989.
  905.  
  906. [Gro89b]
  907.      J. Grosch, Ag - An Attribute  Evaluator  Generator,  Compiler  Generation
  908.      Report  No.  16,  GMD Forschungsstelle an der Universitat Karlsruhe, Aug.
  909.      1989.
  910.  
  911. [GrE90]
  912.      J. Grosch and H. Emmelmann, A Tool Box for  Compiler  Construction,  LNCS
  913.      477, (Oct. 1990), 106-116, Springer Verlag.
  914.  
  915. [Kas80]
  916.      U. Kastens, Ordered Attribute Grammars, Acta Inf. 13, 3 (1980), 229-256.
  917.  
  918. [Knu68]
  919.      D. E. Knuth, Semantics of Context-Free  Languages,  Mathematical  Systems
  920.      Theory 2, 2 (June 1968), 127-146.
  921.  
  922. [Knu71]
  923.      D.  E.  Knuth,   Semantics   of   Context-free   Languages:   Correction,
  924.      Mathematical Systems Theory 5, (Mar. 1971), 95-96.
  925.  
  926. [Mar90]
  927.      M. Martin, Entwurf und Implementierung  eines  Ubersetzers  von  Modula-2
  928.      nach  C, Diplomarbeit, GMD Forschungsstelle an der Universitat Karlsruhe,
  929.      Feb. 1990.
  930.  
  931. [Vie89]
  932.      B.  Vielsack,  Spezifikation  und  Implementierung   der   Transformation
  933.      attributierter   Baume,   Diplomarbeit,   GMD   Forschungsstelle  an  der
  934.      Universitat Karlsruhe, June 1989.
  935.  
  936. [VSK89]
  937.      H. H. Vogt, S. D. Swierstra and M.  F.  Kuiper,  Higher  Order  Attribute
  938.  
  939.  
  940.  
  941.  
  942.  
  943.  
  944.  
  945.  
  946.  
  947.  
  948.                                                                             12
  949.  
  950.  
  951.      Grammars, SIGPLAN Notices 24, 7 (July 1989), 131-145.
  952.  
  953. [Wir88a]
  954.      N. Wirth, Type Extensions, ACM Trans. Prog. Lang. and Systems 10, 2 (Apr.
  955.      1988), 204-214.
  956.  
  957. [Wir88b]
  958.      N. Wirth, The Programming Language Oberon, Software-Practice & Experience
  959.      18, 7 (July 1988), 671-690.
  960.  
  961. [Wir88c]
  962.      N. Wirth, From Modula to Oberon, Software-Practice  &  Experience  18,  7
  963.      (July 1988), 661-670.
  964.  
  965.  
  966.  
  967.  
  968.  
  969.  
  970.  
  971.  
  972.  
  973.  
  974.  
  975.  
  976.  
  977.  
  978.  
  979.  
  980.  
  981.  
  982.  
  983.  
  984.  
  985.  
  986.  
  987.  
  988.  
  989.  
  990.  
  991.  
  992.  
  993.  
  994.  
  995.  
  996.  
  997.  
  998.  
  999.  
  1000.  
  1001.  
  1002.  
  1003.  
  1004.  
  1005.  
  1006.  
  1007.  
  1008.  
  1009.  
  1010.  
  1011.  
  1012.  
  1013.                                                                              1
  1014.  
  1015.  
  1016. Contents
  1017.  
  1018.         Abstract ........................................................    1
  1019. 1.      Introduction ....................................................    1
  1020. 2.      Definition ......................................................    2
  1021. 3.      Examples ........................................................    3
  1022. 4.      Comparison ......................................................    6
  1023. 4.1.    Attribute Grammars ..............................................    7
  1024. 4.2.    Trees and Records ...............................................    7
  1025. 4.3.    Type Extensions .................................................    8
  1026. 4.4.    Object-Oriented Programming .....................................    8
  1027. 5.      Experiences .....................................................    8
  1028. 6.      Summary .........................................................   10
  1029.         References ......................................................   10
  1030.  
  1031.  
  1032.  
  1033.  
  1034.  
  1035.  
  1036.  
  1037.  
  1038.  
  1039.  
  1040.  
  1041.  
  1042.  
  1043.  
  1044.  
  1045.  
  1046.  
  1047.  
  1048.  
  1049.  
  1050.  
  1051.  
  1052.  
  1053.  
  1054.  
  1055.  
  1056.  
  1057.  
  1058.  
  1059.  
  1060.  
  1061.  
  1062.  
  1063.  
  1064.  
  1065.  
  1066.  
  1067.  
  1068.  
  1069.  
  1070.  
  1071.  
  1072.  
  1073.  
  1074.